from typing import List


class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast, size = 0, 1, len(nums)
        while fast < size:
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
        return slow + 1

    def removeElement(self, nums: List[int], val: int) -> int:
        slow, fast, size = 0, 0, len(nums)
        while fast < size:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = self.removeElement(nums, 0)
        for i in range(k, len(nums)):
            nums[i] = 0

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left + 1, right + 1]
            elif sum < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]

    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s = s.reverse()

    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        res = ""
        for i in range(size):
            lStr = self.getPalindrome(s, i, i)
            rStr = self.getPalindrome(s, i, i + 1)
            res = lStr if len(lStr) > len(res) else res
            res = rStr if len(rStr) > len(res) else res
        return res

    def getPalindrome(self, str, left, right):
        size = len(str)
        while left >= 0 and right < size and str[left] == str[right]:
            left -= 1
            right += 1
        return str[left + 1:right]


    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        self.diff = [0] * n
        for booking in bookings:
            self.diffIncrease(booking)

        return self.diffResult()

    def diffIncrease(self, booking):
        self.diff[booking[0] - 1] += booking[2]
        if booking[1] < len(self.diff):
            self.diff[booking[1]] -= booking[2]

    def diffResult(self) -> List[int]:
        n = len(self.diff)
        result = [self.diff[0]] * n
        for i in range(1, n):
            result[i] = result[i - 1] + self.diff[i]
        return result

    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        toMax = 0
        for trip in trips:
            toMax = max(toMax, trip[2])
        length = toMax + 1
        diff = [0] * length
        for trip in trips:
            diff[trip[1]] += trip[0]
            diff[trip[2]] -= trip[0]

        people = 0
        for i in range(length):
            people += diff[i]
            if people > capacity:
                return False
        return True

    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 按对角线反转
        row, col = len(matrix), len(matrix[0])
        for i in range(row):
            for j in range(i):
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp
        # 按行反转
        for i in range(row):
            self.reverse(matrix[i])

    def reverse(self, row):
        i, j = 0, len(row) - 1
        while i < j:
            temp = row[i]
            row[i] = row[j]
            row[j] = temp
            j -= 1
            i += 1

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        count = m * n
        leftBound, upperBound, rightBound, bottomBound = 0, 0, n - 1, m - 1
        list = []
        while len(list) < count:
            if upperBound <= bottomBound:
                for i in range(leftBound, rightBound + 1):
                    list.append(matrix[upperBound][i])
                upperBound += 1
            if leftBound <= rightBound:
                for i in range(upperBound, bottomBound + 1):
                    list.append(matrix[i][rightBound])
                rightBound -= 1
            if upperBound <= bottomBound:
                for i in range(rightBound, leftBound - 1, -1):
                    list.append(matrix[bottomBound][i])
                bottomBound -= 1
            if leftBound <= rightBound:
                for i in range(bottomBound, upperBound - 1, -1):
                    list.append(matrix[i][leftBound])
                leftBound += 1
        return list

class NumArray:

    def __init__(self, nums: List[int]):
        length = len(nums)
        self.preSums = [0] * (length + 1)
        for i in range(1, length + 1):
            self.preSums[i] = self.preSums[i - 1] + nums[i - 1]


    def sumRange(self, left: int, right: int) -> int:
        return self.preSums[right + 1] - self.preSums[left]

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.preSums = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.preSums[i][j] = self.preSums[i - 1][j] + self.preSums[i][j - 1] - self.preSums[i - 1][j - 1] + matrix[i - 1][j - 1]


    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSums[row2 + 1][col2 + 1] - self.preSums[row2 + 1][col1] - self.preSums[row1][col2 + 1] + self.preSums[row1][col1]

# 差分数组工具类
class Difference:
    def __init__(self, nums: List[int]):
        length = len(nums)
        self.diff = [nums[0]] * length
        for i in range(1, length):
            self.diff[i] = nums[i] - nums[i - 1]

    def increase(self, start: int, end: int, value: int):
        self.diff[start] += value
        if end + 1 < len(self.diff):
            self.diff[end + 1] -= value

    def result(self) -> List[int]:
        length = len(self.diff)
        result = [self.diff[0]] * length
        for i in range(1, length):
            result[i] = self.diff[i] + result[i - 1]
        return result


if __name__ == '__main__':
    diff = Difference([0] * 5)
    updates = [[1,3,2],[2,4,3],[0,2,-2]]
    for subList in updates:
        diff.increase(subList[0], subList[1], subList[2])
    print(diff.result())